#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

struct Interval {
     int start;
     int end;
     Interval() : start(0), end(0) {}
     Interval(int s, int e) : start(s), end(e) {}
};

bool myComp(const Interval &lhs, const Interval &rhs)
{
    return lhs.start  != rhs.start ? lhs.start < rhs.start : lhs.end < rhs.end;
}
 
class Solution {
     public:
         vector<Interval> merge(vector<Interval> &intervals) {
             vector<Interval> ans;
             if (intervals.size() == 0) return ans;
             if (intervals.size() == 1) return intervals;

             sort(intervals.begin(), intervals.end(), myComp);
             int start = intervals[0].start;
             int end = intervals[0].end;
             cout  << start << " " << endl;
             for (int i = 1; i < intervals.size(); i++) {
                if (end < intervals[i].start) {
                    ans.push_back(Interval(start, end));
                    start = intervals[i].start;
                    end = intervals[i].end;
                } else {
                    end = max(intervals[i].end, end);
                }
             }
             ans.push_back(Interval(start, end));
             return ans; 
         }
};

//test in 1337 online judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;

    cout << "-----------------Test 1--------------------" << endl;
    vector<Interval> myVec;
    myVec.push_back(Interval(1,4));
    myVec.push_back(Interval(0,4));
    vector<Interval> result = mySolution.merge(myVec);
    for (int i = 0; i < result.size(); i++) {
        cout << result[i].start << " " << result[i].end << endl;
    }

    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
